n=5000;
m=1000;
id=[9731,8551,5371,1465,8056,4765,5752,4114,4600,4155,6643,6874,6504,9340,3753,5057,5531,8987,8021,3639,7090,1009,7512,7767,6290,4591,5216,5879,2059,2838,5352,3585,9016,6847,4340,8614,3373,7127,1624,2831,3626,4991,8734,7216,8708,1763,4821,7403,9149,3507,3615,6732,6271,8483,3184,8397,1040,3780,5437,9425,2597,8705,9578,6138,6490,4631,5313,2933,9181,3987,5604,6599,6408,5927,3686,8060,2543,3970,6805,5729,9199,4742,2937,7540,5984,1425,7042,5803,6549,4049,4412,4692,8102,1492,9808,7584,5182,9900,6041,4271,4915,9189,1426,8194,4016,9304,2801,2040,9740,1349,8430,1987,7133,8188,8595,2514,1312,6705,9180,8862,8797,8123,5139,7797,7356,7242,9692,4630,5395,4395,9160,8145,2388,1504,9924,1713,5054,4389,7132,1757,4691,2986,2269,9773,1626,8478,2246,8353,8669,9300,9352,5928,4624,4704,7222,6083,4440,4474,6905,6355,9321,4428,9245,8425,7183,2601,2424,2995,1511,1462,9435,7389,4992,1778,4165,3116,4380,5882,6489,3873,8905,1237,5901,5977,3467,7406,4024,2675,8156,5358,1968,9918,7080,2506,8410,7239,2748,1680,3340,6119,3342,7190,1648,1377,6640,6811,3998,3299,2657,7202,3935,1891,9987,9335,6008,9116,7654,9412,7385,3944,2505,2476,5548,1260,9354,1721,8714,3805,1088,6247,9928,7602,7221,4749,5208,5184,9520,4540,9649,9262,5712,5083,6738,7417,6467,6984,8216,3138,6946,2932,7808,1054,6448,4860,4595,5615,3051,6052,7794,7697,5456,8579,4851,1921,9849,4722,9085,7286,2000,9134,7974,5640,3458,5253,4178,4231,4121,3452,3194,7111,6213,9206,8318,5168,1307,9747,2537,8688,8709,7026,8827,7580,5298,8091,4565,2261,8233,8124,5621,9253,5087,5714,4725,8975,3618,3182,6563,1094,3976,7627,7793,2908,4929,1779,5756,5263,9182,7946,4076,4709,5514,4022,4518,4250,9758,1234,4854,3628,4972,3222,1733,9574,5268,4997,7526,8666,6051,5743,7069,2340,4334,2202,7648,4598,9794,1711,9673,7982,8291,9926,1266,2131,4597,3188,4643,9004,7890,1791,8485,6283,4064,2745,4401,9831,3332,8199,2826,6517,1021,2299,9604,3026,2876,2351,6346,3406,1044,5642,4310,3704,6264,4040,5697,5651,3974,6029,4562,5911,4646,9878,5963,5921,2091,2289,3271,7168,3526,4384,8154,2978,7235,4881,2974,1311,4682,4721,3664,5275,6683,7570,6415,1409,8493,4102,8833,3165,2098,3401,5639,9108,9567,4372,6426,9240,5704,7472,7854,6475,8306,1755,1993,9997,6681,9082,1068,5273,4544,1394,8876,3577,3897,7464,8345,2905,4700,9228,9287,4988,4783,3737,5198,5111,6449,5719,4037,2923,7833,4143,7708,1039,4637,2716,6729,2175,2133,3292,2171,6704,5018,1114,4665,4578,6178,4805,5133,1015,1837,9092,7152,7096,7293,9625,9859,2430,6999,5392,4301,3872,5278,4998,3245,2722,9838,4995,1043,7506,1525,7088,5797,1379,6755,9619,6165,3968,7240,9220,1104,7980,2764,4714,2623,1506,5763,7788,4202,7244,8723,4809,4683,6822,8220,2481,9533,3914,2893,8193,5388,1748,4671,4399,2641,2948,3557,2348,7957,3451,5574,6665,9962,5375,7749,6401,1495,1796,9422,3721,2328,8488,7515,6480,1749,1539,3170,4892,4523,7838,4801,5865,1957,1160,5446,9853,2511,7031,2878,6810,2085,2423,3100,1986,6036,1850,7485,3878,4791,3597,1572,6864,1588,6046,2154,2313,2549,2454,5608,8742,8546,1631,8918,8232,8562,8502,9029,9710,1611,1655,2885,3259,1998,9419,2554,8809,2535,4815,9224,1499,7136,4651,3821,4884,6062,6313,3098,9782,5376,2021,8673,9815,2238,5107,6170,7929,8999,7546,7603,8268,6113,8519,4052,2387,9705,8913,1435,7203,6327,7578,1145,5549,2027,5973,7576,5447,8333,5409,3865,7670,2512,6431,1731,7467,8057,5389,8455,9474,2720,3783,8925,9812,2196,4589,3150,5906,7664,2310,1166,3602,6775,2735,4280,4806,8446,2070,3145,1994,6322,3339,2547,8703,2159,4260,8919,4217,1149,9588,4167,8223,3708,9177,6955,3301,5042,2739,9449,9494,5397,2650,8762,9187,1530,6796,4126,9562,6155,3946,3502,5065,3296,6509,5611,4510,4612,1227,9921,1084,2574,4830,7089,6005,1456,2146,1407,1723,4807,1209,3648,1183,9101,4148,4760,2834,9941,7097,4096,3902,6414,9641,4896,1338,7605,1124,9049,6829,4225,8403,4077,5051,1767,6797,4822,5491,5255,4741,5391,9542,4207,8592,6820,3803,2977,9643,7253,6093,4046,6252,5325,4681,7564,8240,7072,9800,7847,9618,7626,3334,8189,7895,6988,1354,2262,9995,9426,2867,6904,5512,2087,9657,2767,3759,7453,5241,1115,5453,2566,8825,7129,1479,7316,9874,3032,1608,5558,3394,4868,8507,8095,5571,3647,5041,5040,6527,7542,5061,8477,7503,5635,3550,8522,3685,5673,9267,9695,5455,7077,7377,1760,1180,8093,3251,9005,2945,6206,1562,1992,3348,4984,7554,2596,5023,3411,8155,2830,3104,4777,5942,9458,4226,6790,6357,5335,4852,9447,6929,5766,5568,4398,4425,6457,5676,4038,5086,4900,8677,7742,3325,6856,6389,1060,7270,8560,5726,2497,3041,5941,1049,4044,4442,7812,4672,9624,2832,9845,8991,2705,2645,6212,7347,8810,9296,7383,5687,9623,6804,7158,6394,1469,5644,1649,1587,4379,8989,4054,8431,6193,5949,9635,4893,4736,8475,2296,7620,6241,5100,9151,6379,9675,2990,2478,9930,1947,6852,7714,4245,9272,5101,9460,5525,1141,6642,7841,6081,4238,5387,6084,2142,4954,5092,4904,8657,9437,9172,1224,2522,8587,1319,6371,8454,6773,3351,7696,4091,1972,8202,7965,5883,7494,3738,4448,3541,1089,8010,7822,2100,8211,3089,8365,1904,8509,1565,8427,6731,8022,8735,1991,2165,7869,9477,8984,1664,5022,6176,9147,6879,8094,7820,9459,1330,1087,9405,2281,7295,5768,5975,8531,8631,7816,5585,8122,2868,8112,4032,8085,8130,9018,9438,1280,1549,6934,1146,2139,9032,1474,8018,7631,6349,1790,6986,3079,5462,9990,2791,4312,7716,3644,8289,3049,5507,5126,5581,7448,7213,2815,7185,9774,4342,4416,5232,2588,6399,9334,1932,3662,9137,6225,1905,6075,4107,9757,1315,4184,2663,1450,1516,2513,5089,4652,4869,4339,7804,1139,3337,1143,7553,2436,2486,5231,4450,6667,2605,7873,6189,3781,1116,2132,1910,4364,1940,2083,6186,9485,2147,1639,7614,1196,6141,1692,3297,9036,3910,8857,4219,6370,7912,6848,9960,3725,2003,5469,5196,9097,9904,3005,4958,4752,2308,9946,9028,5892,7806,6388,8757,2989,4971,1480,3454,2330,6793,7498,3688,2842,8334,7224,9746,2934,1953,4960,5163,9148,2858,2089,4259,2966,5612,8508,1902,2732,3671,8191,2239,4043,8197,9076,5031,8545,4856,8637,3022,4890,5957,4221,5876,9862,4104,6374,1797,6169,9948,1876,5864,3837,3722,4772,2920,2203,4632,3444,2851,4131,8928,4042,2493,1997,2591,2206,4703,3439,7024,9197,8436,5284,9645,9605,8838,1571,3981,2584,9527,2930,9945,2020,1897,1302,6588,8449,5747,7883,3496,2014,9495,7659,5946,3216,7376,2570,6995,3752,6604,1016,3494,2190,1665,1159,5177,9201,9077,1263,6664,2036,8030,5354,9084,9479,6660,9353,9935,9392,5573,6040,7184,1981,1623,4800,8961,5193,7046,3126,3449,1609,7881,7004,1248,5274,1459,8382,2696,3884,4017,3059,1034,9452,4895,1128,5795,5843,2804,4686,2334,7707,1201,5151,6380,6689,6219,7790,8941,3326,9842,8700,2618,3167,3670,9927,9867,2263,1287,2350,8895,7532,8969,4055,2057,6765,5682,7673,1126,7961,9203,7766,4099,5659,8055,8744,4891,5728,6541,7916,8957,1535,1526,4177,5867,4070,1544,2672,8456,3353,4837,1318,2794,3807,5156,3591,1824,1222,2136,1567,9011,7993,1148,3829,7177,6458,8920,4585,1644,4779,8995,4235,4642,6481,4905,8399,8988,4796,4172,7769,2377,7062,4705,1339,3236,4824,4675,5679,6981,4078,8970,7782,4653,8550,1702,5224,3835,1599,3247,9484,1866,8845,5905,5908,5423,5826,6880,4898,2469,2232,3718,8428,3514,3621,3926,3484,4634,7486,1189,3757,1194,1221,9185,4381,8107,5486,8887,6433,2242,4502,4352,1063,4994,3364,3019,2884,7799,9145,8269,6750,6770,7312,7083,1950,2929,7930,2665,4361,5143,5717,4504,1306,5115,4242,3132,3298,9793,7505,7175,9840,5844,3171,2010,2221,4570,1329,9223,2820,8958,6661,9952,1123,2719,7703,7832,1795,7374,8129,4470,7076,7234,8569,5071,9417,8347,2352,2698,1543,2041,7200,5989,5259,9691,8381,8792,2223,5808,3572,6248,5742,4558,1625,2067,1654,6973,8121,7773,5937,9111,1519,4927,2218,3495,1117,1327,3773,6368,6103,7889,3576,9526,2466,3249,3241,4127,8136,7774,9727,2981,2336,8956,7781,7038,5290,5454,6756,7171,9584,7143,8356,9978,4575,6784,4735,4872,8045,3480,3233,3312,2560,6535,5032,3455,8375,4587,5235,5451,5220,7966,8668,1700,4018,2482,6816,5855,7533,4786,8500,3540,7635,9051,2162,8313,3013,8996,3962,1689,7860,2164,5285,7479,3855,2195,8521,9026,1008,9996,8118,4640,8426,3633,7636,1607,5078,4689,9472,2614,3754,5922,5312,6954,4376,7601,7364,4240,6369,5204,7103,3408,3922,7227,9915,7306,6454,2758,2523,6898,7675,1390,1597,1369,8540,1482,1633,2004,7911,1059,3000,8971,2013,4731,7810,2571,8568,6071,9703,2902,7008,1554,4117,5831,7108,3887,8250,6526,7052,6968,3336,2635,8749,5164,2047,5632,5985,1548,8326,6931,8316,2822,1328,2253,5432,3838,9688,8554,8922,5771,1440,3959,2465,2453,9869,3767,9042,7473,9798,2395,6392,3923,2813,3417,1100,7514,3370,7840,1007,4094,3979,6824,8444,4909,4460,7199,7751,6516,4539,7893,7529,4874,9064,1844,7094,4694,2703,4132,4433,5056,3925,1264,8111,7851,7836,6967,7523,2347,7267,2097,2081,3932,3083,4282,6952,7135,4281,7968,2141,7044,9656,6020,5463,2470,1708,3861,5958,9593,3522,4170,7118,6721,2279,2733,5090,1357,4555,7354,7238,7994,4648,2428,4166,6353,9556,7452,2849,5653,3518,5664,6823,8262,4422,7421,1112,6096,9448,2019,5357,6496,8774,6003,7830,2323,2364,7353,7689,1812,6179,8081,6853,7898,8638,2972,5415,8288,6098,2286,7012,7555,8210,7987,4547,4451,8209,3934,5780,6089,4708,8633,4430,8340,7904,6558,1213,2008,8439,9973,3429,3587,3971,1745,1256,9726,7692,3215,2556,7826,8070,7986,6435,2647,6596,6876,2785,9007,1600,7572,1370,2504,9785,6381,4810,1927,1382,7995,9124,7747,2770,5019,3799,4613,5024,9242,9857,4432,3015,6220,5798,4789,8387,2379,3472,1928,2166,9389,3596,4480,7325,4011,1873,5420,6375,7271,8280,9702,1615,1271,4844,1019,4969,4309,5105,2054,3703,8875,8617,9195,7159,3432,9281,7391,6679,5248,1423,8207,7538,6974,7181,1434,9544,5840,9701,7819,5972,8151,6199,4521,3273,7879,1083,9098,8676,6077,5685,5523,9234,1712,1709,3859,7269,9165,9167,6701,7825,9820,1062,1754,5725,3160,7618,5361,6234,1523,5557,5696,9046,4137,3713,5443,6243,6644,4522,4101,3523,9951,8266,2048,4729,6393,2772,1661,6114,1965,8567,4189,3761,8917,7530,6117,6216,7757,9797,4248,2446,7859,8824,3266,7877,4059,5570,2130,9630,6182,4307,7298,2294,2970,9292,7594,3581,5662,2243,9964,3477,3927,1468,6827,8407,3842,8405,5127,1915,2529,2225,4115,6217,5769,8885,2561,3529,4305,2994,6129,5048,8050,8258,9977,8565,2869,9566,3844,7754,6238,5689,2148,5195,8746,4359,3877,4916,6112,3751,6580,6257,5767,3391,9652,3828,2854,1962,6633,5939,6675,8498,1305,2030,6782,8858,5318,4110,2888,2128,1867,5996,9453,9344,2143,5859,7517,7035,2541,3590,4390,8886,9212,4569,1182,9789,6548,1322,8954,6860,4756,8108,4948,1414,6321,3871,8114,9089,9529,8729,8358,8153,4392,2006,9947,6993,2987,4963,3383,9756,3814,6983,8467,5020,3787,6754,9672,1170,7372,8897,9282,9748,3208,1688,6985,7084,8505,1490,2837,2863,5738,1862,5174,9730,9855,3130,6270,1734,4875,9558,1590,5616,6110,6579,1065,1518,9202,8338,6104,4323,8815,2692,5960,4626,8681,3242,1335,1020,6976,6233,5050,1403,9983,7207,5480,1193,5656,4941,2755,5501,1323,3893,4707,1598,6739,1282,2210,1233,9480,4277,8601,4716,8249,2052,3909,9462,1238,4886,3674,7014,3995,5329,5693,6766,8363,5026,1362,6935,3470,3771,9661,1347,7073,9319,9232,7078,9677,8647,2102,6109,9939,3196,5349,7679,8234,3428,6432,1348,2314,2011,7189,2363,4405,1568,1975,9466,7259,3546,2988,3687,7588,7104,2587,4053,2119,5407,5093,7695,4549,9903,6659,1805,5889,2568,6398,9471,7324,4740,6166,7704,6727,4625,8513,1892,9510,4919,5979,5252,5713,9639,3035,7630,4739,6292,3263,2539,9386,1153,7510,3425,7558,6690,8814,2916,5828,4901,3191,6298,7229,7370,8846,7632,6202,1046,5452,5700,7358,5390,3672,6413,4862,5961,8826,8615,4163,6018,3044,2825,1579,2564,4647,9427,5368,6091,7678,3476,8802,4065,8349,4553,4619,3588,2316,5677,5701,6687,8882,7641,1249,4014,2824,9274,4377,2325,4322,9229,8570,4552,3189,1244,6969,7857,2546,8559,3660,9999,2118,9415,8552,9326,9589,5554,9943,5394,4514,8068,8231,2492,2324,7397,3964,6518,5770,1005,1621,1367,6452,5884,3218,6397,3134,1758,8398,9992,1513,3875,5500,5821,6996,1825,2761,2173,7913,8942,8074,9910,3599,8780,6552,3293,8539,8143,8389,2189,2257,9892,1080,7115,6963,7894,5215,6870,4003,9759,1936,1852,8960,5530,6317,5692,4455,3209,4546,8765,4534,4286,7480,3717,7647,9336,1524,9689,3640,4531,1026,2248,9538,4590,5629,2980,6769,3945,1163,4746,1596,5474,9233,7291,5812,9784,7443,5641,6263,7057,3155,4119,4839,8821,2997,2250,1582,2821,8741,4855,2267,4069,3084,2392,7474,1848,2402,8806,6013,7779,9390,9548,6106,9409,5526,2273,1294,2843,6323,4727,3809,7141,6305,1800,9674,2170,7301,8994,6798,5509,4253,1422,8131,8626,4885,5427,9284,9456,2305,9152,6198,1604,5279,7054,8113,9467,5683,3309,7328,8263,6164,3260,4913,1267,8205,6172,9000,6158,4133,3949,5777,8606,9489,3225,5119,4889,3054,9025,2186,9932,2528,3256,2724,8725,7950,6027,4744,7566,6950,2608,6672,3584,9198,6629,6060,6461,8943,1373,7548,9132,2107,5043,4649,8620,4005,9162,9565,9045,3544,1834,7706,1105,2416,2660,5000,1061,9144,2088,4434,7212,4715,9043,2306,7650,9665,4461,3812,9035,5250,5081,9537,3503,4251,6136,3226,8219,1132,8704,2134,9732,3586,4151,6126,8946,6019,6471,1452,2163,3840,9893,3795,4051,8208,7741,1578,3183,4659,5690,5444,6841,6576,2500,9521,8092,7719,6911,2715,9662,4469,4781,9022,9497,1446,2954,6342,2664,1725,3504,1178,2616,8033,8261,8750,2654,3017,5848,2538,8803,9015,6223,9235,6989,7432,4775,4842,4545,5282,4478,1775,8800,5626,7475,9288,2637,5508,4229,6099,1337,6593,8192,5270,7037,4699,9421,2656,3202,2809,5829,4444,2396,9868,8149,4135,7112,9563,2856,8369,4427,1821,3177,2412,3734,9196,5149,5909,6329,1274,5539,3255,6175,9765,3564,9795,3459,7768,4566,8760,9949,6840,2405,5595,6913,1433,2475,5527,3936,2399,5109,6605,3042,2993,6072,7935,8277,7138,1620,4408,7907,9579,9237,8859,2138,9414,1540,5589,2642,6591,6924,2076,3136,5410,5004,3735,8360,4370,2044,9356,9879,8867,5981,7960,4944,6771,6142,9807,3985,3016,1750,4467,4798,1672,4680,9104,8117,4462,9473,2874,3895,8766,7496,4966,2444,5814,2479,3638,7531,4463,6464,2686,3852,6559,2280,3027,2374,4641,1239,7776,3667,4382,9761,3152,7075,9887,4224,2532,6556,3159,2921,1360,7281,5737,6533,7991,6786,5968,4391,1716,5878,5851,8883,6802,7243,9963,7821,7276,1746,3217,7918,8236,7745,4437,8598,3052,2679,4793,2298,1467,9053,8099,3729,5817,4274,5099,7845,8610,4008,2227,1285,9736,3229,2401,9001,9219,5471,1017,5189,6044,2742,9400,2426,3832,3867,6520,4303,2439,3573,9324,4666,5622,8359,6447,9933,2200,1901,2617,6192,4175,4458,7079,4829,6465,2862,1916,9682,6221,5722,8344,4861,5482,7320,3306,2765,5333,1584,7848,6272,5686,5902,3497,3211,2661,8048,9464,6268,9434,1613,5067,8470,7855,5610,4698,2604,8487,9975,9492,3304,6411,9373,4931,9884,8167,8937,4062,2914,2431,2353,4195,2215,3355,8379,6649,3272,5881,1471,2515,3343,9809,2509,2907,4543,6575,4500,6127,6451,3404,5694,5173,6014,2976,7426,8756,5744,2774,3067,4468,6183,3996,7344,4608,9993,1018,7169,2971,2108,7173,3707,8848,8028,3485,5667,7992,2018,3748,5856,9586,1079,1421,9398,1652,7011,2517,7254,8597,2231,5691,7470,9208,9468,6887,7567,6614,1675,1581,9733,8649,1575,5165,3020,4243,8794,2684,1710,2699,2459,1736,9362,9150,6049,9827,4144,6190,2700,7905,3764,4084,9886,7892,6107,4499,6511,4873,4617,4026,6587,7068,6638,5799,2544,3166,9014,6589,1662,9788,3006,7010,7248,7188,1818,2871,6826,9142,9431,7800,7658,8259,8604,9751,9506,8948,9099,8067,3848,3864,3967,1476,9209,5191,2456,9986,8822,8982,6914,6653,3834,1069,2593,9443,3641,8593,6668,1637,2285,7146,2632,8541,5365,4505,9919,6586,5244,9895,6422,8655,5590,7941,5823,7937,6167,6674,1484,4550,8252,3849,2787,5417,3125,5782,5359,5010,5336,8712,1417,8670,8031,8017,4436,2413,7634,1385,4712,5746,4204,6868,8314,4021,6063,6307,3912,9441,3511,5775,4770,6424,4501,1809,9115,6741,7652,6745,5620,4476,2092,3701,3179,8282,4953,8902,4212,3663,1460,1669,7952,6628,5894,9937,6242,6148,7953,7521,8930,4420,9889,1507,3124,3405,5888,2565,1395,3943,3466,3536,8715,4538,8273,4877,3652,6808,3863,4095,8707,3607,9810,2153,6472,4790,6016,7064,8501,6168,2371,9090,7971,2578,9664,5448,7710,5113,1413,4088,9259,7289,9171,2950,7441,4222,4074,7231,5008,9524,9880,2975,4278,6779,5434,8312,5827,8661,1186,1576,3960,3107,8769,3025,4007,4713,2818,1173,4429,1942,7738,9836,9576,4973,7613,3898,4582,3973,1614,4141,8040,4197,6177,3322,5393,2550,1216,6287,6149,9778,2418,3374,8464,6420,1279,7018,2673,7582,7977,8923,5027,3482,4159,8308,2483,1610,3565,9072,9509,7940,6921,6926,5262,7330,7699,5711,2114,5754,1030,8873,4265,3818,5330,5545,7721,1780,2378,6512,2548,3549,6330,9554,3435,5230,7764,4325,5070,8622,1432,5403,5577,5597,1658,8931,4833,7765,8125,8588,4223,5045,1185,7645,9444,1545,1855,5668,5154,8007,4938,8730,7761,9882,2743,8175,5202,5269,4010,9871,6284,3205,8861,6632,7623,8406,8198,8807,4957,6351,9848,6354,1871,1718,9275,8038,9315,1428,6191,5751,6095,9418,7917,2609,5120,1276,9283,6412,7414,7502,6508,5535,5197,4763,7341,3103,3377,2865,3500,3612,6067,6688,2406,5449,3766,6421,5846,1976,5077,8100,6001,5924,1699,2304,9984,8422,5327,2678,1290,8819,6908,1184,9813,1025,8457,2941,8645,9163,8981,3419,3115,7497,3677,2695,1010,4355,1334,1739,9368,6572,2167,1772,2861,4118,6753,8442,9052,1875,3190,5288,6692,2062,7029,1108,1693,1747,5246,1341,1822,6622,9553,5755,8648,7815,5326,7471,7245,1500,6792,2819,6210,8998,9755,8265,8870,3913,5870,1296,8026,9021,1899,7958,7998,8172,9423,9839,3384,9629,7186,9087,3827,1314,3556,3316,7061,9522,8315,6513,3038,7795,4079,3111,2109,6400,3908,9699,1284,2372,5665,1378,3889,7939,1591,8228,1364,7552,6617,6028,9033,3238,4048,9829,3916,9341,1841,9351,5049,9173,2926,2222,6061,6590,5893,3412,5904,6523,2193,1913,6423,3706,9290,9956,6295,3357,2892,7415,9923,1455,9308,2066,1085,3106,5130,5791,1963,8752,6564,2145,9094,6196,4288,5430,2636,5576,1003,1635,7001,9110,7628,5058,9739,4156,1752,9716,6693,2367,4579,2485,6445,1240,2326,3221,1914,9050,6325,3537,7482,2026,5978,1359,7367,1188,9013,3119,5029,1142,5281,4139,1111,8461,3930,2806,5847,2847,2045,9818,2373,9210,9130,7303,9457,8159,7579,9006,2461,6358,1728,4559,5424,7463,3318,4181,1133,4914,8710,6111,3139,9603,1697,2318,6053,5655,7612,9074,7422,2376,6839,4533,9366,6814,7335,1412,8720,6462,6785,3833,4036,6122,2606,8073,8299,6861,3505,4687,7927,4899,6348,8664,3219,2252,9610,9091,6634,4524,4134,5839,9314,9901,7586,3161,9241,7925,6372,6542,2090,2760,6280,8206,8116,1889,7813,1542,3043,9971,5903,2551,8307,3028,4396,5584,7451,8466,5014,1893,3181,9631,9766,7340,6635,4409,4009,9377,7814,1786,4272,7021,4845,2198,9038,2063,2480,2149,4400,9342,2542,1103,8443,9394,9207,5898,8082,7272,8695,3696,9067,7191,8495,8537,1601,6235,4346,4507,4688,6764,1956,7442,8748,9518,5986,9564,7551,4593,5473,5011,3475,9966,9546,4262,7305,5102,4664,6335,7246,9347,5708,9413,7178,8429,6842,9037,5476,6396,7336,3492,8613,5309,6282,6300,5720,9178,9114,8674,4940,2391,3099,6245,9246,6492,5405,9487,5987,2803,6249,3066,7215,5583,9534,5970,8656,7034,4799,9864,6144,1995,4075,9003,1439,5073,7962,5116,4983,8793,7834,1313,8458,4495,2172,2211,2357,5233,7140,2358,6387,5541,1058,9621,6222,1645,5807,6425,5772,1945,6578,6214,9609,4497,7906,2295,3594,9762,3896,8924,2900,3955,5276,6714,1684,7137,7161,3742,2463,4604,2687,5618,4888,4728,3684,5614,1714,3774,9214,9511,4527,6228,8135,4787,4256,2327,3147,9920,8581,1487,5128,6352,7375,8691,8851,3243,2283,7373,4677,5869,5561,9648,3709,2610,2622,9557,3331,4605,7983,7611,9381,4109,2721,7217,9113,8388,4182,1013,4574,4464,7619,7228,3954,7201,2005,6680,7667,8052,9096,5580,5124,4103,8043,8120,6185,8150,2233,3060,8582,3080,6619,7469,6362,7725,2039,7226,7668,1293,1404,3788,6043,2002,9503,3071,4747,1391,7368,7455,6011,4085,8420,6941,4662,7606,8869,3003,1920,8041,2845,7700,7300,9260,5013,7491,3740,5716,6616,5505,7182,5428,1751,5994,8013,2194,3224,6673,6890,7720,7798,2053,5025,4089,3409,7119,1979,5347,3034,6697,4188,1304,2913,1488,8627,6730,9779,8653,3756,1150,8503,8543,4061,7663,6965,2555,5951,3378,6611,7978,6932,3798,4402,4357,1217,7556,6783,9059,2355,3823,5342,5123,9047,2582,1534,6340,5537,9159,1344,9622,8479,1536,5810,2384,7861,2032,1741,6294,2953,7125,6514,9938,9683,4168,6978,5492,6869,9907,8643,5419,9088,6584,5472,2464,8075,2525,8520,9153,8607,4780,3490,7672,7775,8836,4629,5227,3891,6015,4297,1138,3953,1081,7102,8871,7232,5378,5214,1744,5654,7735,8225,1934,6429,1073,4541,5373,2244,1272,1074,3164,2359,2779,8024,3123,6455,5613,1070,3804,3931,9596,4738,3381,7481,4214,8759,7020,7559,6838,1203,2001,9790,6326,5718,6909,6118,7030,1977,6997,8866,3509,6237,1210,8408,5649,7507,9254,2895,6227,8343,1969,8686,7865,9369,6042,7691,2297,4535,9817,2007,9498,1002,3281,9865,2160,3158,6724,5186,9659,1783,3499,8035,1396,4811,7736,6545,8603,1602,1047,5830,2414,8053,9704,4863,1895,4457,2754,7780,6474,5085,4769,5200,3977,9685,5362,1147,1832,6173,4782,8678,4563,2105,8004,4987,7622,5524,7440,9481,4171,2859,8976,2762,2205,1346,5167,8778,4907,3785,4013,5239,5680,4108,6720,7688,7206,3262,4199,8109,4311,8071,5990,5672,4925,1356,2643,3317,5796,9247,1531,4849,5515,2709,7006,7972,4160,5669,8763,9646,6312,5818,9805,2691,4314,9693,3046,1292,3589,7334,9676,3095,9469,3999,1122,4241,3605,4407,6338,3267,4337,5698,7005,2077,6626,8281,7022,3881,8350,9204,7607,5226,6363,1376,6618,8801,5479,8036,9357,7142,6943,9306,5038,7277,2763,1698,6163,2251,3086,8544,3519,9226,7604,3739,3808,1857,6320,1380,5272,4880,8927,2619,9508,8201,8573,4607,3775,7285,4616,8972,9637,1595,8591,7241,9908,6087,8302,6930,6560,7308,1283,7388,4247,3275,1880,6915,6964,6972,2017,2321,8574,2043,2586,9069,4838,3593,3442,2212,9183,5152,8936,4814,3438,1072,5404,8837,8438,5816,2901,7154,9309,8357,6125,8069,4918,5131,4603,9745,1175,4477,1647,4921,8944,1985,8243,8891,8006,5384,4734,2015,5144,8934,7315,9445,3520,7348,8719,7273,9823,6279,6627,9030,8771,7709,5413,1930,6737,9023,9781,7989,1794,3542,1332,7644,5740,1777,1606,8856,7868,7060,3489,4449,5134,8538,2093,9093,3430,9694,9258,4623,1200,4766,8817,4060,5055,5681,7786,8298,1389,3371,6139,3957,4621,9488,3029,5316,4556,7560,8840,1208,4588,1448,3114,5733,6047,4622,6893,8105,3624,4835,7150,4471,1787,5991,4324,5147,6021,9446,2333,5088,2939,4551,4757,1515,9802,8235,8279,7490,4269,5245,3206,6140,3352,1420,2241,5750,6900,4252,4244,5952,3929,4773,3625,2646,9370,9998,6501,3515,8754,8798,3561,5897,1121,3354,6478,1098,1533,2471,1954,2204,6998,8371,4317,7346,7640,7151,3919,5724,7131,9363,4774,9917,5910,1933,1033,4090,9034,5317,5331,8632,8713,1288,6205,3244,4934,9571,1167,5983,2860,9515,4568,3760,3137,1261,6832,2169,5106,1593,6948,2229,3382,1686,8037,5959,5236,9536,2343,2887,7728,7777,1052,5346,8571,1868,5594,8530,7758,1151,9799,1481,5118,5003,9898,7979,6723,9136,6064,2284,5280,5556,4183,1884,9768,9581,1405,4443,5301,7500,5522,9650,8843,3090,4492,8536,3608,7888,4564,3483,5338,8787,2872,1242,6718,3762,5982,1463,5650,9543,3510,2457,2016,7789,4759,3290,6817,6384,5436,2012,9866,7047,8532,3924,6536,9117,1235,6953,2897,2501,4669,3277,9009,3004,6854,2891,4491,3531,7296,1286,5084,3732,6807,4082,1176,6297,3857,2287,1729,7237,8773,8401,7317,4939,1687,9897,1670,2516,6991,9597,9349,8226,3386,8415,8914,1814,6749,5351,7105,9129,8731,5321,2508,6440,4198,6105,9863,1557,5435,5228,9231,2873,5891,9329,1444,3265,2558,5161,4394,9514,8002,6877,7805,7680,4210,5076,2429,8654,1140,6120,8578,4047,2581,9922,2383,3087,5348,8687,1853,1820,7723,7386,9502,8042,3826,5059,7920,4373,7339,6296,8652,1784,7337,3178,9912,2680,1246,6314,1498,8679,3300,4258,9131,7400,6265,5560,6713,4654,3113,7365,3692,9276,9279,5225,1168,3421,5890,3851,9505,5381,3195,8008,4255,6979,2425,8576,8888,4417,7657,1856,2474,5609,4459,2219,2594,4004,2288,1592,7534,9382,7595,7016,7842,1343,3232,5956,5520,5104,9403,9192,4668,7361,5938,4029,9027,4284,9106,4748,6522,9601,6878,2766,8938,9931,6097,2793,1555,1137,1415,1438,7561,9890,2184,5625,9322,6746,9176,2575,5425,1882,4576,6022,5256,7379,6337,3156,5072,9217,8831,7746,9289,3825,6809,2427,8063,1627,1381,8580,3330,1886,6162,5845,7195,5481,3457,8224,3448,8301,5727,1250,3234,9343,4015,9822,9154,3609,2644,5053,3903,5360,9251,9139,7550,1944,2652,7702,9519,4138,1983,7187,7608,8142,2667,7416,7589,2886,6966,7760,8951,9482,1722,1269,8594,6767,8906,6430,3498,4917,9644,7036,8964,6818,9112,6343,4924,9054,3487,9861,8370,7874,5396,3966,4965,1988,4254,9133,4843,6128,1245,6336,9594,9911,5033,4028,7824,5631,8963,3426,7948,4072,5993,6048,1527,9270,4710,3534,2607,9883,8915,5967,1667,4511,9638,5699,3268,2086,3993,2342,7351,4947,1694,2890,9123,4403,1436,3061,5592,4676,6975,8090,9346,3110,5528,5854,2853,6623,4636,8362,4350,4572,3743,5172,2331,8743,5636,7801,2438,5137,4827,8889,9269,9244,5587,9580,3112,5315,5332,7110,2999,3009,2256,1793,8680,1961,6776,5784,1630,7943,4930,9012,6273,9404,5142,5929,7569,1431,9126,6889,4767,3192,1978,7932,7387,2534,4057,9175,4937,6677,9361,3347,8404,8134,8616,4200,2422,9841,5915,3076,5037,8717,4315,7180,6918,9470,3070,8911,2747,2666,9230,8865,8983,2611,3901,2398,3631,5422,5180,7055,3862,7829,1951,7915,6197,1704,8949,6910,8585,1833,6859,9261,6982,9450,3846,9976,6706,1091,3817,9236,8181,4454,1206,4876,4706,8528,8515,6694,4656,4678,4516,3723,3989,9345,8993,7170,2356,3388,2224,7511,3264,7130,5129,4162,1218,3204,9465,1130,7360,5477,5593,6685,3169,8611,6416,7549,5926,8671,2432,8182,1429,6959,2693,2638,9811,4685,6306,3637,7082,9491,6698,7160,9325,7543,4985,5418,1926,9174,9166,3784,9170,7449,7257,1829,8564,2234,8516,9651,9660,6607,9569,6319,1960,4697,6529,4348,2084,6815,3646,2659,3303,2073,8482,9539,5320,4234,7730,8164,8096,5964,7013,5190,3329,4803,8272,4112,3392,5645,5379,1119,3885,3462,7908,6866,6073,4124,1342,3643,5498,3288,1461,4192,7230,3033,8110,7934,4418,8469,6987,5567,8640,1505,5211,8783,7547,2959,1813,5470,9858,4196,8786,5237,7019,8820,7871,6682,2271,2956,8323,3888,8238,3579,3294,2807,9791,1268,3656,1340,5110,7059,4321,7197,1127,8384,2009,6652,6402,9310,1001,9303,4650,4410,4980,1847,1402,7743,8775,5467,8179,5586,1443];
score=[85,72,85,75,89,91,77,89,78,82,89,80,98,54,91,99,75,78,71,85,70,89,80,48,85,90,49,85,59,75,72,66,73,85,81,88,81,70,78,94,82,86,74,90,43,91,51,89,93,98,87,79,77,70,52,80,44,78,55,95,98,91,61,91,76,62,76,88,98,85,60,97,79,76,54,57,95,86,73,78,87,86,74,78,85,85,82,96,58,68,84,70,66,88,70,93,74,75,89,43,75,75,71,81,80,76,71,84,72,83,80,99,73,90,100,75,70,76,87,82,94,46,74,82,94,84,70,85,92,80,72,79,73,84,54,71,82,62,81,77,72,92,87,88,82,74,74,99,78,85,89,96,86,93,87,61,86,78,81,78,70,77,91,83,77,88,86,70,77,78,72,85,87,90,73,95,82,97,72,81,84,74,94,82,73,70,73,84,71,72,84,77,85,40,81,80,92,83,89,78,81,72,83,81,100,83,62,81,98,75,66,58,51,74,100,85,88,52,88,60,83,91,74,75,86,76,71,97,81,85,74,46,59,93,75,72,54,40,71,87,82,89,78,94,84,73,88,85,88,72,78,84,83,87,80,53,100,89,92,56,78,83,72,41,75,62,97,79,44,81,59,76,87,47,83,81,79,83,72,81,41,86,89,40,72,49,84,86,85,75,78,74,89,83,100,48,89,86,86,73,89,84,74,87,62,82,91,87,84,96,77,45,71,86,63,63,83,57,84,72,97,72,100,95,86,47,80,86,88,73,75,95,71,99,73,73,72,97,95,57,82,84,75,70,73,77,80,80,71,75,87,88,59,86,87,91,88,81,73,85,72,77,83,84,44,89,83,73,73,87,70,88,70,93,96,76,72,81,76,88,83,71,70,41,82,75,98,86,92,75,77,72,81,47,52,97,62,80,76,88,66,70,72,82,73,90,75,83,97,79,100,62,82,89,76,62,72,94,81,87,70,75,92,83,70,72,54,86,75,94,77,81,43,61,44,79,85,78,43,73,73,90,95,87,94,76,89,76,77,41,87,85,70,79,93,80,84,42,75,42,73,71,89,94,72,79,65,91,95,86,77,85,83,95,89,74,88,58,54,86,76,73,79,97,80,70,91,95,94,83,85,95,75,84,93,80,91,74,50,91,78,78,85,81,81,79,75,53,87,72,74,87,71,57,74,64,79,97,74,70,97,78,40,89,96,79,74,77,79,49,53,91,83,90,84,81,89,78,80,71,90,99,85,74,96,90,88,42,89,81,72,87,80,70,96,60,93,86,72,81,85,64,88,83,79,45,87,83,91,75,86,56,100,85,83,80,42,75,71,81,72,99,59,52,44,96,89,82,55,79,67,65,81,69,48,75,88,92,88,72,94,73,84,81,78,73,92,81,87,81,85,52,97,80,71,59,72,100,58,91,80,88,74,66,45,82,74,85,98,85,82,99,76,96,62,82,72,70,60,72,85,75,77,82,64,74,90,88,79,89,97,86,59,87,89,59,51,82,82,72,87,72,73,51,74,89,85,87,94,73,82,74,51,81,42,83,84,75,88,76,92,78,76,79,95,78,88,77,99,73,43,89,93,82,78,81,74,50,80,86,80,80,74,96,77,79,51,73,71,99,72,93,64,59,88,72,83,90,43,98,79,46,82,75,94,87,44,77,82,89,71,70,90,80,98,99,98,70,72,73,79,94,82,86,93,70,72,80,47,85,72,85,70,72,94,83,88,74,71,73,71,75,79,89,83,85,79,48,80,84,81,93,95,89,92,90,88,85,91,80,87,72,81,95,71,87,71,66,76,73,97,86,85,78,87,96,48,76,98,82,50,79,49,82,77,78,63,78,83,71,66,75,79,72,82,99,83,82,71,98,70,83,77,72,87,87,87,86,85,83,86,96,82,73,87,98,98,71,98,57,83,70,76,100,87,81,85,82,62,74,77,72,89,68,68,96,75,70,71,45,40,80,82,78,94,84,79,89,86,78,74,89,80,83,85,76,79,71,76,75,88,86,85,96,71,88,81,85,90,66,84,48,64,77,86,85,72,74,70,89,79,73,78,95,78,87,99,86,91,86,90,65,73,77,84,82,78,83,83,84,76,71,85,73,86,72,97,100,61,53,79,83,98,79,49,77,72,76,86,88,78,86,88,93,95,81,85,83,79,82,70,40,74,89,97,74,83,88,79,84,81,80,74,94,100,55,74,71,88,76,88,90,77,63,85,87,71,61,59,82,91,83,42,76,73,46,73,90,75,88,77,68,77,83,96,64,86,53,70,88,88,73,87,82,42,86,77,98,76,77,87,78,44,53,88,92,99,74,83,41,78,42,89,86,89,70,64,47,70,82,79,83,73,77,74,78,70,77,77,88,58,85,95,92,84,79,93,49,76,86,51,95,97,85,90,74,100,63,78,88,84,88,78,77,78,83,82,86,99,68,71,77,78,73,98,76,96,73,72,81,46,97,84,95,89,99,65,81,88,96,47,62,80,51,96,85,85,79,86,50,93,92,86,64,88,89,100,77,75,75,69,80,80,95,83,89,89,86,95,94,100,87,82,80,86,45,80,85,72,76,74,88,93,82,75,70,80,77,73,87,79,61,76,87,78,73,86,83,99,72,70,75,87,98,100,85,82,88,74,85,45,84,83,93,75,43,84,79,93,89,64,80,94,71,43,75,74,81,93,91,43,90,57,89,76,89,70,83,88,97,86,74,90,74,75,89,81,70,72,82,85,90,40,85,95,81,78,83,74,96,70,73,77,64,52,71,73,89,76,82,87,83,88,76,98,70,85,83,87,76,75,95,82,74,97,81,85,75,85,54,99,83,97,81,80,81,92,90,88,93,72,79,50,80,66,94,74,81,86,80,76,82,70,67,77,94,84,85,84,80,73,70,82,97,83,81,86,75,79,89,86,83,63,58,75,87,68,47,65,77,84,73,69,74,72,78,52,75,71,76,57,76,91,72,84,40,42,77,80,79,82,74,93,47,75,78,76,46,71,76,82,100,82,81,92,87,61,83,85,87,88,52,92,98,86,78,72,76,73,72,42,65,76,81,48,82,86,72,61,83,56,80,79,79,76,43,79,85,93,71,73,84,99,85,76,89,86,85,84,88,87,45,64,94,89,87,76,86,88,87,75,60,78,85,95,70,71,89,91,72,95,77,68,84,44,98,71,50,84,77,86,75,80,85,77,61,78,84,100,78,72,88,61,63,67,74,87,70,44,72,80,50,95,74,94,95,64,73,91,86,70,70,88,71,83,83,83,41,74,79,40,53,82,87,74,70,77,87,75,85,81,74,98,82,71,74,86,74,66,59,100,73,83,92,83,97,93,48,80,84,90,77,77,57,99,87,79,88,81,70,83,97,77,93,73,68,69,88,85,70,79,75,73,93,48,76,78,90,88,67,81,77,69,89,70,53,89,76,99,88,70,92,76,72,89,78,88,87,99,98,79,87,78,90,48,91,96,70,90,89,79,92,97,88,98,42,83,81,73,71,77,88,89,60,91,88,65,75,80,80,75,72,52,72,79,80,92,77,93,88,58,81,74,74,97,84,100,86,82,55,81,72,91,71,52,71,85,87,82,95,88,63,41,73,84,89,82,72,75,93,91,99,86,80,86,73,75,91,87,74,72,81,78,70,47,89,73,84,84,44,67,92,96,97,86,70,86,91,72,60,50,49,79,75,89,89,82,77,71,75,83,80,85,85,70,66,88,99,88,61,69,83,76,91,74,79,72,61,75,63,88,95,87,65,83,87,73,54,87,71,87,86,91,85,67,77,97,88,85,91,79,82,86,72,63,96,77,72,70,86,84,77,70,83,85,96,48,80,86,57,75,74,87,78,46,73,79,81,57,87,75,73,72,76,88,61,71,87,84,89,71,74,79,86,65,70,78,81,69,86,87,64,84,84,71,88,70,47,73,78,100,83,88,52,83,87,61,76,53,42,70,72,97,76,64,43,82,78,72,72,83,76,93,85,96,81,44,78,87,84,81,70,92,94,86,81,78,74,68,71,84,80,81,84,90,74,85,97,71,80,76,93,72,74,72,72,79,70,77,65,63,100,88,86,76,81,90,69,53,86,87,76,97,70,75,45,82,81,54,40,59,87,98,71,87,95,84,85,61,83,89,82,79,82,89,83,82,74,80,81,81,64,84,75,70,83,77,79,76,84,74,76,81,68,82,92,83,97,92,73,71,87,94,91,70,74,78,79,78,89,75,61,55,83,50,89,85,64,83,52,74,94,79,73,97,92,75,86,76,98,82,74,78,78,92,86,46,69,73,84,84,89,85,73,78,93,89,84,94,81,81,74,61,72,87,71,75,45,75,84,82,74,42,43,89,93,92,73,74,75,76,81,85,83,94,73,76,87,88,95,67,77,100,71,71,94,66,94,72,77,100,95,97,53,75,93,84,81,92,86,83,100,95,94,72,86,81,77,79,91,57,85,95,72,83,73,45,94,79,78,61,80,75,89,99,55,75,82,79,95,49,72,71,91,73,78,91,72,80,72,84,89,86,74,82,45,88,52,70,96,83,68,57,73,84,84,54,95,88,88,87,77,79,86,70,67,71,67,85,94,85,74,70,80,62,86,71,70,57,77,99,75,97,82,89,83,82,71,85,52,54,76,83,78,57,70,97,71,49,72,79,48,92,82,97,59,53,44,80,80,82,90,85,63,88,100,71,75,94,84,82,82,72,73,50,71,75,87,75,77,51,55,87,88,48,78,78,89,79,79,78,78,74,48,78,74,73,86,83,76,49,50,81,90,98,77,91,46,80,53,73,82,84,74,86,83,70,77,89,79,41,67,71,72,83,72,60,59,89,88,99,87,53,44,85,98,71,87,99,72,81,80,70,78,70,71,79,80,86,83,84,73,81,93,78,89,71,80,70,93,53,56,75,96,95,86,70,88,80,71,71,93,78,84,70,72,41,72,93,70,75,76,59,99,83,41,84,77,79,62,88,93,58,84,78,82,82,72,48,78,77,89,41,75,71,85,81,94,46,85,94,82,69,77,87,78,82,55,99,81,67,90,91,86,98,82,88,52,72,81,80,84,80,89,71,100,72,88,76,84,81,59,79,88,84,80,82,50,70,85,62,81,60,73,72,78,79,67,44,53,90,77,52,71,95,87,67,96,94,87,78,82,78,76,91,83,76,78,86,70,56,85,78,62,82,77,77,72,72,71,74,86,80,53,83,83,53,91,79,87,94,94,99,70,74,81,82,72,98,83,88,43,72,93,81,79,77,87,73,81,73,82,79,83,87,85,86,45,72,41,70,80,73,73,88,85,84,71,46,97,87,56,100,72,78,76,73,81,84,78,92,80,72,88,78,81,76,86,87,71,57,59,82,85,81,75,99,83,50,84,82,78,99,87,72,78,81,82,82,83,53,82,83,46,52,100,83,76,78,86,91,76,66,99,77,74,81,87,83,71,74,86,85,45,86,82,70,91,73,86,61,81,92,91,72,86,71,73,62,85,79,89,77,54,55,46,77,42,92,75,74,66,94,76,79,74,87,84,73,84,50,73,76,82,80,59,86,92,70,84,88,72,85,79,70,81,93,100,89,96,87,85,80,71,84,81,75,92,89,72,74,79,71,89,73,82,74,100,70,46,98,90,80,72,89,81,50,75,91,90,86,86,71,90,96,79,48,45,100,76,89,72,75,76,59,88,71,87,88,77,74,78,93,93,97,86,83,89,92,87,96,74,78,98,62,75,77,53,72,73,74,95,99,93,82,80,80,56,94,70,68,82,89,77,70,72,72,95,56,84,80,47,80,95,76,75,84,88,81,78,83,51,84,89,78,57,87,70,80,98,79,74,72,88,72,94,95,91,87,78,84,87,78,67,50,73,94,43,79,82,76,81,88,96,86,80,75,89,85,43,90,84,85,84,89,88,98,86,87,82,76,43,71,88,85,77,76,70,83,87,55,89,79,41,72,59,73,84,78,91,68,93,91,79,88,45,41,80,79,72,71,77,42,77,62,95,48,86,77,55,85,76,80,73,85,80,83,77,96,44,49,84,72,63,41,87,96,51,76,70,83,77,52,59,78,86,83,44,80,76,90,99,69,81,78,96,68,87,73,83,99,73,100,87,70,76,76,99,79,70,89,77,71,84,53,72,70,78,97,75,94,75,94,85,74,77,72,76,78,96,89,85,82,58,100,72,89,72,72,55,53,75,86,76,70,91,85,87,89,74,97,72,40,43,72,74,61,77,81,55,100,73,92,80,98,77,85,88,73,67,45,70,71,80,86,81,76,71,81,74,78,81,70,89,40,83,77,85,72,95,83,72,81,84,61,50,70,67,100,71,71,82,71,79,87,93,78,75,70,54,68,86,73,73,88,73,89,79,74,40,80,71,95,51,87,85,84,72,83,93,71,96,73,76,51,83,84,100,75,78,83,97,97,96,93,54,88,64,78,99,47,41,76,74,81,71,91,77,96,71,87,74,75,83,82,78,76,80,61,64,87,82,87,84,77,77,83,96,52,94,88,70,86,94,100,84,82,71,70,72,74,77,77,79,85,80,71,43,76,79,87,70,87,75,79,71,84,48,96,82,96,43,79,100,78,78,88,82,94,67,40,81,75,84,96,96,50,75,56,65,77,89,64,81,86,89,92,100,74,76,52,46,83,87,88,79,86,71,85,83,71,85,60,80,88,83,84,89,81,64,78,77,95,98,62,59,86,76,80,80,97,72,94,87,82,60,61,44,79,70,92,72,84,72,76,94,75,77,85,78,95,75,90,49,90,65,73,77,67,76,78,75,46,83,50,89,83,80,46,42,97,88,80,76,84,75,49,79,84,56,66,97,77,84,55,61,90,81,87,70,50,85,86,80,76,71,53,83,74,78,73,86,83,97,91,84,52,72,84,87,73,95,78,64,94,58,87,72,90,83,86,86,71,87,98,94,85,79,67,76,86,86,93,71,71,55,84,84,50,74,77,94,85,70,68,95,72,87,76,75,78,74,74,75,74,98,82,81,61,57,91,82,77,57,42,89,83,89,78,79,94,73,92,77,65,89,88,76,83,67,41,81,71,88,89,100,84,93,81,78,72,92,77,89,99,80,42,94,84,65,85,81,96,85,85,76,92,46,47,81,87,78,71,90,96,76,89,91,78,89,91,89,78,83,70,86,87,73,95,64,82,74,88,88,78,74,83,58,42,71,76,95,89,86,76,99,94,66,73,85,89,83,55,75,92,87,81,97,49,70,98,85,89,88,83,81,77,44,77,78,83,82,94,88,81,85,75,81,57,70,86,79,90,71,73,92,89,59,86,81,73,89,87,73,73,72,87,83,80,55,71,76,80,77,80,48,82,79,79,93,58,54,51,78,40,84,95,100,71,88,86,83,88,90,41,45,85,78,87,87,87,41,84,82,80,81,82,82,89,84,88,80,95,88,72,79,70,73,96,76,64,76,76,93,51,58,80,92,70,70,75,72,77,61,88,85,88,98,78,59,79,42,61,40,67,86,41,72,83,92,87,42,83,90,80,83,80,87,76,72,72,57,84,84,75,55,75,100,58,99,59,85,70,84,53,98,82,86,87,95,89,88,81,75,70,92,83,77,100,83,82,44,93,81,77,91,86,68,70,45,74,71,78,98,67,100,90,84,86,80,81,95,74,85,91,84,71,77,80,81,52,78,76,88,83,87,82,83,79,43,84,68,70,79,95,79,85,88,78,80,43,76,71,74,86,83,100,66,91,74,96,75,93,76,85,87,94,79,58,90,85,72,89,82,98,86,70,99,86,80,78,73,85,71,70,77,71,70,75,78,82,86,47,86,79,77,74,57,85,78,74,88,71,55,81,90,86,70,70,88,76,76,41,86,88,95,77,93,83,78,70,71,71,67,95,91,79,89,81,84,75,68,84,89,62,83,81,92,50,73,80,42,84,87,100,100,61,64,72,83,84,79,85,99,58,84,75,98,85,90,89,76,93,77,99,75,89,71,77,84,60,43,84,99,86,72,82,86,68,74,92,81,42,74,83,77,71,85,83,57,53,78,57,74,77,85,100,44,56,81,79,76,54,91,87,80,81,77,83,84,43,85,80,79,84,81,80,77,77,82,93,68,86,80,81,98,86,80,60,84,49,76,45,71,87,89,72,93,83,98,81,80,75,70,92,84,87,89,89,85,99,45,79,73,78,42,73,82,79,81,80,97,84,96,58,73,70,77,91,88,56,80,89,83,82,72,55,89,99,79,76,74,89,90,70,78,87,55,71,70,77,92,97,52,76,41,53,73,84,77,76,86,71,82,70,72,89,51,100,89,86,73,75,79,88,85,72,72,70,70,85,77,96,84,79,87,76,96,78,79,89,77,80,86,86,75,80,97,73,88,57,73,81,73,74,78,77,78,84,83,83,72,41,100,80,57,84,70,42,74,95,76,57,77,97,83,87,79,44,78,99,81,55,73,84,92,88,75,85,87,54,58,78,80,90,82,68,76,80,58,76,86,88,76,75,42,71,70,42,70,77,44,100,97,82,56,75,49,45,71,76,84,97,79,56,90,89,80,70,75,85,82,80,65,93,42,72,82,70,97,78,42,83,75,71,73,91,78,70,74,89,73,78,81,74,83,76,47,73,78,64,76,87,72,79,54,87,71,41,86,75,85,97,78,79,74,79,84,71,89,84,91,89,94,79,79,95,55,96,99,96,98,99,87,80,43,71,51,71,75,93,87,86,50,72,78,80,97,79,89,70,70,78,71,80,70,86,72,75,85,86,73,89,99,87,99,54,73,86,98,91,77,81,71,76,74,70,63,64,70,73,90,100,84,84,92,74,84,72,74,55,70,74,77,73,55,48,80,76,73,49,71,99,97,60,88,48,84,50,84,86,87,75,86,84,43,93,83,76,94,69,79,85,76,84,72,70,75,85,45,94,89,80,89,88,84,77,72,82,81,71,51,74,85,100,81,80,85,88,83,85,77,77,65,90,84,87,78,89,80,87,89,82,48,62,73,57,74,75,81,87,75,82,78,55,100,73,65,88,93,85,59,91,87,92,75,88,82,76,65,85,61,86,74,94,83,84,70,66,94,85,78,60,70,83,74,84,63,58,56,76,81,100,87,76,75,45,84,80,81,79,98,86,79,64,90,85,73,79,59,78,77,76,86,71,51,95,84,96,89,83,98,77,84,68,82,75,82,81,78,89,74,72,71,80,100,87,79,64,83,53,78,82,86,55,83,98,96,71,78,79,76,49,75,54,79,81,50,91,76,84,88,61,99,57,92,88,76,84,91,84,89,78,74,85,86,88,76,91,70,74,100,91,89,80,49,87,73,81,92,87,80,42,74,63,84,87,75,95,80,67,40,63,74,88,71,79,80,73,92,41,83,58,87,94,89,88,77,67,75,46,70,80,65,43,80,71,86,95,65,51,96,62,97,78,71,89,77,72,73,88,82,76,87,98,78,73,94,48,82,43,88,82,78,72,76,78,82,78,57,89,87,79,77,74,74,75,75,83,76,89,77,82,43,77,84,80,72,64,85,95,95,89,85,82,78,71,68,73,80,75,74,83,81,54,86,96,99,92,79,97,88,77,71,78,80,84,78,82,67,93,55,90,72,75,82,78,80,96,98,74,90,66,44,96,83,78,72,94,76,82,66,73,77,49,54,86,82,92,74,77,73,83,74,96,98,82,91,86,75,90,71,42,49,76,75,92,44,70,78,83,92,96,81,81,67,75,83,60,83,73,97,83,67,82,82,83,70,85,85,68,50,55,83,100,51,76,81,76,83,83,73,86,68,86,79,86,83,89,81,78,72,69,47,86,71,83,74,98,82,85,89,81,43,86,85,82,85,82,88,77,96,85,45,78,74,100,59,70,87,75,94,85,93,88,94,47,84,81,83,81,97,52,84,72,81,78,81,71,76,79,76,48,44,96,94,79,46,71,87,70,88,79,76,80,83,71,49,96,89,72,84,71,99,77,62,71,68,89,81,99,74,82,74,88,63,78,73,80,92,71,76,46,75,79,46,74,91,80,89,86,91,73,86,78,87,85,80,93,88,76,75,84,100,75,100,83,85,80,86,98,87,82,77,86,78,79,86,99,91,71,99,98,75,83,81,86,49,82,81,81,77,90,87,80,72,57,94,87,72,92,76,94,94,70,85,89,71,77,73,77,72,85,85,81,97,74,76,82,52,87,94,71,87,71,74,93,78,66,81,85,74,98,82,74,82,86,73,89,72,71,100,79,70,77,78,71,92,50,83,84,92,80,83,85,48,68,87,91,89,97,78,61,79,95,89,55,70,75,80,88,71,84,73,84,75,95,72,83,73,84,40,48,100,82,83,76,82,76,71,76,42,71,87,69,76,82,81,81,97,40,83,49,83,73,97,92,99,66,83,81,79,97,50,73,82,88,83,94,100,83,52,54,94,80,43,75,83,94,77,87,70,85,85,78,88,77,81,78,83,51,81,72,77,67,70,63,62,74,78,93,78,43,99,96,48,83,84,84,43,73,49,95,76,78,44,72,60,76,80,76,94,93,83,94,78,73,79,74,81,80,81,81,86,83,75,88,93,84,74,83,87,76,82,71,96,80,92,75,45,62,86,88,69,71,84,81,86,52,78,83,72,94,61,78,70,84,85,73,76,58,86,84,53,81,84,88,76,78,78,92,77,84,71,83,77,65,81,70,89,77,77,92,73,59,73,43,88,77,93,80,79,86,88,94,87,79,82,89,59,66,87,83,86,85,74,88,87,89,98,80,51,74,72,67,76,78,79,80,82,84,45,74,82,70,55,72,100,78,73,72,68,91,65,85,80,100,80,91,74,80,52,100,88,57,76,73,95,78,76,77,40,76,97,99,81,77,97,95,87,90,89,87,73,74,93,69,75,99,84,44,66,73,76,71,73,93,55,78,84,78,73,93,71,74,94,83,90,48,86,71,76,92,73,79,80,55,71,80,75,76,71,93,74,91,76,75,88,75,78,87,73,97,57,74,72,80,71,96,99,77,74,93,88,80,77,84,85,81,82,95,77,75,96,71,89,63,82,85,74,50,76,90,72,83,81,54,71,77,89,95,65,96,59,89,96,85,68,98,72,73,88,71,61,99,72,95,87,85,73,77,76,86,78,81,73,88,76,74,79,89,53,79,71,87,74,74,89,95,72,91,89,85,58,76,83,51,87,70,78,75,86,93,100,80,77,73,80,74,75,78,76,44,94,44,74,85,71,64,82,70,78,80,85,96,76,68,79,78,99,65,88,58,72,78,72,87,89,78,99,87,85,86,82,71,65,93,96,82,95,87,70,74,77,47,74,78,73,69,77,63,75,79,55,44,72,88,82,75,89];